5.2 Undirected graphs (ugraph)

1. Definition

An instance G of the data type ugraph consists of a set of nodes V and a set of undirected edges E. Every edge e∈E is a set of two nodes {v, w}, v and w are called the endpoints of e. With every node v is associated the list of its adjacent edges adj$\_list$(v) = { e∈E | v∈e }.


2. Creation

G

creates an instance G of type ugraph and initializes it to the empty undirected graph.


3. Operations


Most operations are the same as for directed graphs. The following operations are either additional or have different effects.


& truecm & truecm & node opposite node v, edge e returns w if e = {v, w}, nil otherwise

int degree node v returns the degree of node v.

edge new_edge node v, node w inserts the undirected edge {v, w} into G by appending it to the adjacency lists of both v and w and returns it

edge new_edge node v, node w, edge e1, edge e2, dir1=after, dir2=after inserts the undirected edge {v, w} after (if dir1 = after) or before (if dir1 = before) the edge e1 into the adjacency list of v and after (if dir2 = after) or before (if dir2 = before) the edge e2 into the adjacency list of w and returns it

edge adj_succ edge e, node v returns the successor of edge e in the adjacency list of v.

edge adj_pred edge e, node v returns the predecessor of edge e in the adjacency list of v.

edge cyclic_adj_succ edge e, node v returns the cyclic successor of edge e in the adjacency list of v.

edge cyclic_adj_pred edge e, node v returns the cyclic predecessor of edge e in the adjacency list of v.


4. Implementation

Undirected graphs are implemented like directed graphs by adjacency lists. The adjacency list of a node v contains all edges {v, w} of the graph. Most operations take constant time, except of all_nodes, all_edges, del_all_nodes, del_all_edges, clear, write, and read which take time O(n + m), where n is the current number of nodes and m is the current number of edges. The space requirement is O(n + m).